%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require Positive integer $n$.
\Ensure A random binary tree on $n$ vertices.
%%
%% algorithm body
\If{$n = 1$}
  \State \Return $K_1$
\EndIf
\State $v \gets 0$
\State $T \gets$ null graph
\State add $v$ to $T$
\State $\MyParent \gets [(v,0)]$
\For{$i \gets 1, 2, \dots, n-1$}
  \State $(v,k) \gets$ remove random element from \MyParent
  \If{$k < 1$}
    \State add $(v, k+1)$ to \MyParent
  \EndIf
  \State add edge $(v, i)$ to $T$
  \State add $(i, 0)$ to \MyParent
\EndFor
\State \Return $T$
\end{algorithmic}
